package 剑指offer;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-11-29 10:02
 * 搜索与回溯算法（中等）
 */
public class day19_64_681_682 {

    /**===========================================================================================================================
     * 剑指 Offer 64. 求1+2+…+n
     * 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     * 1、递归:逻辑运算符的短路性质代替判断
     * 2、快速乘：A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟。其实就是将 B 二进制展开，
     * 如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i) ，即 A<<i。我
     * 们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，这个方法也被称作「俄罗斯农民乘法」
     * */
    public int sumNums1(int n) {
        //当n>0时才会去执行后面的，否则flag会直接赋值为false
        boolean flag=n>0&&(n+=sumNums1(n-1))>0;
        return n;
    }
    int quickMulti(int A,int B){
        int ans = 0;
        for ( ; B>0; B = B>>1) {
            if ((B & 1)>0) {
                ans += A;
            }
            A = A<<1;
        }
        return ans;
    }
    public int sumNums2(int n) {
        //用等差数列求和：n(n+1)>>1
        return quickMulti(n,n+1)>>1;
    }
    //3、将快速乘展开， n 为 [1,10000][1,10000]，所以 n 二进制展开最多不会超过 14 位，我们手动展开 14 层代替循环即可
    public int sumNums(int n) {
        int res=0,A=n,B=n+1;
        boolean flag;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        flag=((B&1)>0)&&((res+=A))>0;
        A<<=1;
        B>>=1;
        return res>>1;
    }

    /**===========================================================================================================================
     * 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 1、递归：二叉搜索树，当p，q分别在root的左右子树时，它是公共祖先，若pq在root的同一边，则它最近公共祖先在root的子树上
     * 2、迭代：找出从root到两个节点的路径，两条路径的分叉点即为最近公共祖先
     * */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null) return null;
        if (root == p || root == q) return root;
        if ((root.val>p.val &&root.val<q.val)||(root.val>q.val&&root.val<p.val)) return root;
        if (root.val>p.val&&root.val>q.val) return lowestCommonAncestor1(root.left,p,q);
        else return lowestCommonAncestor1(root.right,p,q);
    }
    List<TreeNode> getPath(TreeNode root,TreeNode target){
        List<TreeNode> path=new ArrayList<>();
        while (root!=target){
            path.add(root);
            if (target.val<root.val){
                root=root.left;
            }else {
                root=root.right;
            }
        }
        path.add(root);
        return path;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> p_path = getPath(root, p);
        List<TreeNode> q_path = getPath(root, q);
        TreeNode res=null;
        for (int i = 0; i < p_path.size()&&i<q_path.size(); i++) {
            if (p_path.get(i).val==q_path.get(i).val){
                res=p_path.get(i);
            }else {
                break;
            }
        }
        return res;
    }


    /**===========================================================================================================================
     * 剑指 Offer 68 - II. 二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 递归：情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点。
     *      情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗。
     *      情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。
     * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //base case
        if (root==null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点。
        if (left!=null&&right!=null) return root;

        //情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗。
        if (left==null&&right==null) return null;

        //情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。
        return left==null?right:left;

    }
}
